package 数据结构.BinaryTree;

public class BinaryTreeNode {
    private int data;
    private BinaryTreeNode leftChild;
    private BinaryTreeNode rightChild;

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public BinaryTreeNode getLeftChild() {
        return leftChild;
    }

    public void setLeftChild(BinaryTreeNode leftChild) {
        this.leftChild = leftChild;
    }

    public BinaryTreeNode getRightChild() {
        return rightChild;
    }

    public void setRightChild(BinaryTreeNode rightChild) {
        this.rightChild = rightChild;
    }

    public static class BinaryTree {
        private BinaryTreeNode root;

        public BinaryTreeNode getRoot() {
            return root;
        }

        public void setRoot(BinaryTreeNode root) {
            this.root = root;
        }

        public void BinaryTreeNode(BinaryTreeNode root) {
            this.root = root;
        }

        //一.清空二叉树的两种方法
        //递归
        //1.清空以这个节点为根节点的树【删除这个节点下面的树结构】
        //这个清楚的方法是想要去删除以这个节点为根节点，要去删掉以这个为根的树
        public void clear(BinaryTreeNode node) {
            if (node != null) {
                clear(node.leftChild);
                clear(node.rightChild);
                node = null;
            }
        }

        //2.清空根节点为节点的树【从root节点开始删起】
        //这个是要删掉所有
        public void clear() {
            //传root节点过去
            clear(root);
        }

        //二.判断树是否为空
        //如果根节点为空，那么就是空了
        public Boolean isEmpty() {
            return root == null;
        }

        //二.求二叉树的高度
        //1.得到 传某个以这个节点为根节点的树
        //todo：1.注意这些加后的结果是不是有继承下去：如何在递归中这些叠加后结果有继承呢，
        // 就是 return 回来,并且要有变量去接收：int leftHigh=high(node.leftChild);
        //      2，要+1【因为在算的时候是以某段树的左子树和右子树的数量去算的，然后要加上这段树的根节点，才能得到真正的高度/节点树】
        public Integer high(BinaryTreeNode node) {
            //去判断这个节点是不是null，如果不是null +1
            //然后去判断这个节点的左子节点/右子节点是不是null，注意：只能加一次1
            //我的思路：只让二叉树去走左子树/右子树：这样子的bug：得到的不一定是对的，
            // 我们要得到的树是最长的那个【但如果刚开始是走了左子树但实际上是右子树比较长，所以不行】
            /*            if(node!=null){
                if(node.leftChild!=null){
                    high(node.leftChild,high);
                }else {
                    if(node.rightChild!=null){
                        high(node.rightChild,high);
                    }
                }
                high++;
            }
            return high;*/
            //正确思路：直接去走两条路 最后那条最长的就是高度了
            if (node == null) {
                return 0;
            } else {
                //记得要接收返回来的高度
                //左子树的高度
                int leftHigh = high(node.leftChild);
                //右子树的高度
                int rightHigh = high(node.rightChild);
                //高度应该算更高的一边，（+1是因为要算上自身这一层）
                return Math.max(leftHigh, rightHigh) + 1;
            }
        }

        //2.这个是去得到整个树的高度
        public Integer high() {
            return high(root);
        }

        //三.求二叉树的节点数
        //1.算以node为根节点的下面的节点数
        //节点 是什么？ 如果节点不为null，那么就得算
        public Integer nodeNum(BinaryTreeNode node) {
            if (node == null) {
                return 0;
            } else {
                //得到左字数的节点数量
                int leftNum = nodeNum(node.leftChild);
                //右子树的节点数量
                int rightNum = nodeNum(node.rightChild);
                //两个相加然后再+1【这个1其实就是某段树的根节点】
                return leftNum + rightNum + 1;
            }
        }

        //2.算整树的节点数
        public Integer nodeNum() {

            return nodeNum(root);
        }

        //返回某节点的父节点
        //todo：递归的想法：普适性，即要适用递归 之后的
        //node节点在subTree子树中的父节点
        //subTree就是某个树的根节点
        //这个树可能是很前的根节点 。。
        //todo：递归的方法其实就是：可以想象一下
        //                            1.我这个方法如果是最终调用时的结果的时候怎么写，
        //                            2.如果不是怎么写
        //                            3.在递归方法的下面，如果递归没结束，是不会执行到下面的方法的
        //                            4.每一次递归调用的方法的下面的方法，也会执行
        public BinaryTreeNode getParent(BinaryTreeNode subTree, BinaryTreeNode node) {
            //如果subTree为null，那么则代表着这个树【左/右子树】遍历完了，证明这个树没有所要的父节点，返回null
            if(subTree==null){
                return null;
            }
            //如果判断成功，那么就代表递归有结果了，返回父节点
            if (subTree.getLeftChild() == node || subTree.getRightChild() == node) {
                return subTree;
            }

            //如果递归没有执行到上面的两个return，那么就会一直执行到下面的getParent进行遍历
            //其实递归只会有两种结果：一个是null 一个是父节点subTree
            BinaryTreeNode parent=getParent(subTree.getLeftChild(),node);

            //todo：上面是一直递归会进行递归，当遇到return的时候才会执行到下面的方法。
            //判断是否为null，如果是null则代表左子树没有node节点的父节点
            if(parent!=null){
                return parent;
            }
            //如果上面没有return，那么就证明左子树不行，下面去遍历右子树
            return getParent(subTree.getRightChild(),node);
        }
        //从根节点开始
        public BinaryTreeNode getParent(BinaryTreeNode node){
            return getParent(root,node);
        }

        //返回左右子树
        //返回node节点的左子树
        public BinaryTreeNode getLeftTree(BinaryTreeNode node){
           return node.getLeftChild();

        }
        public BinaryTreeNode gerRightTree(BinaryTreeNode node){
           return node.getRightChild();
        }
        //插入左子树



      /*  public static void main(String[] args) {
            // 创建一个二叉树
            BinaryTree binaryTree = new BinaryTree();

            // 构建一棵二叉树
            BinaryTreeNode root = new BinaryTreeNode();
            root.setData(1);

            BinaryTreeNode leftChild = new BinaryTreeNode();
            leftChild.setData(2);
            BinaryTreeNode rightChild = new BinaryTreeNode();
            rightChild.setData(3);

            root.setLeftChild(leftChild);
            root.setRightChild(rightChild);

            binaryTree.setRoot(root);

            // 测试清空二叉树
            System.out.println("二叉树清空前，是否为空：" + binaryTree.isEmpty());

            binaryTree.clear();

            System.out.println("二叉树清空后，是否为空：" + binaryTree.isEmpty());

            // 重新构建二叉树
            binaryTree.setRoot(root); // 恢复根节点

            // 测试高度计算
            int height = binaryTree.high(root, 1);
            System.out.println("二叉树的高度为：" + height);
        }*/
    }

}
